public class Sort {
    //直接插入排序
    public static void directlyInsertSort(int[] arr) {
        final int Step=1;
        for (int i = Step; i<arr.length; i+=Step) {
            for (int j=i; j>=Step && arr[j]<arr[j - Step];j-=Step) {
                // 交换两个数字
                swap(arr,j - Step,j);
            }
        }
    }

    //分组插入排序、希尔排序
    /**
     * Shellsort, using Shell's (poor) increments.
     * @param arr an array of Comparable items.
     */
    public static void shellsort( int[] arr ) {
        //循环分组
        //分组数量按除2减小
        for( int groupCount = arr.length / 2; groupCount > 0; groupCount /= 2 ) {
            //循环每组
            for (int g = 0; g < groupCount; g++) {
                int gap = groupCount;
                //int num=arr.length/gap;
                //每组内执行插入排序
                for (int i = g * gap + gap; i < arr.length; i += gap) {
                    for (int j = i; j > gap - 1 && arr[j] < arr[j - gap]; j -= gap) {
                        // 交换两个数字
                        swap(arr, j - gap, j);
                    }
                }
            }
        }
    }

    //希尔排序2
    public static <AnyType extends Comparable<? super AnyType>> void shellsort2( AnyType [ ] a ) {
        int j;
        for( int gap = a.length / 2; gap > 0; gap /= 2 ) {
            for (int i = gap; i < a.length; i++) {
                AnyType tmp = a[i];
                for (j = i; j >= gap && tmp.compareTo(a[j - gap]) < 0; j -= gap) {
                    a[j] = a[j - gap];
                }
                a[j] = tmp;
            }
        }
    }


    //快速（交换）排序
    public static void quickSort(int[] arr,int low,int high) {
        int start=low;
        int end=high;

        while (low<high) {
            //基准是low
            while (low<high) {
                if (arr[high]<arr[low]){
                    swap(arr,low,high);
                    //交换后high变为基准
                    low++;
                    break;
                }else{
                    high--;
                }
            }
            //基准是high
            while (low<high) {
                if (arr[low]>arr[high]){
                    swap(arr,low,high);
                    //交换后low变为基准
                    high--;
                    break;
                }else{
                    low++;
                }
            }
        }

        if (low-1>start) {
            quickSort(arr, start, low - 1);
        }
        if (end>high+1) {
            quickSort(arr, high + 1, end);
        }
    }

    public static void quickSort2(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort2(arr, low, pi - 1);
            quickSort2(arr, pi + 1, high);
        }
    }
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    //推排序
    public static void heapSort(int[] arr) {
        int n = arr.length;
        // 构建大根堆
        // 这段代码是构建大根堆的过程，它的循环次数为n/2-1次，是因为在完全二叉树中，叶子节点不需要进行堆化操作，
        // 所以只需要对非叶子节点进行堆化，而非叶子节点的数量为n/2-1个。因此，只需要循环n/2-1次即可完成大根堆的构建。
        // 非叶子节点在一维数组中就是前面 n/2-1
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        // 依次取出堆顶元素，并将余下元素继续堆化，得到有序序列
        for (int i = n - 1; i >= 0; i--) {
            swap(arr, 0, i);
            heapify(arr, i, 0);
        }
    }
    private static void heapify(int[] arr, int heapSize, int i) {
        int largest = i; // 初始化最大值为根节点
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        // 找到左右子节点中的最大值
        if (left < heapSize && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < heapSize && arr[right] > arr[largest]) {
            largest = right;
        }
        // 如果最大值不是根节点，则交换根节点与最大值节点，并递归地对最大值节点进行堆化
        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, heapSize, largest);
        }
    }

    private static void swap(int[] arr,int i,int j){
        /*
        a = a ^ b;//现在a = a ^ b
        b = a ^ b; //b = (a ^ b) ^ b = a ^ (b ^ b) =a
        a = a ^ b;*/
        // 交换两个数字
        if (i!=j) {
            arr[i] = arr[i] ^ arr[j];
            arr[j] = arr[i] ^ arr[j];
            arr[i] = arr[i] ^ arr[j];
        }
    }
}
